SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Recursive language</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Recursive language</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see <a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion (computer science)</a>.</div>

<p>In <a href="Mathematics" title="Mathematics">mathematics</a>, <a href="Logic" title="Logic">logic</a> and <a href="Computer_science" title="Computer science">computer science</a>, a <b>recursive</b> (or <i>decidable</i>) language is a <a href="Recursive_set" class="mw-redirect" title="Recursive set">recursive subset</a> of the <a href="Kleene_closure" class="mw-redirect" title="Kleene closure">Kleene closure</a> of an <a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">alphabet</a>. Equivalently, a <a href="Formal_language" title="Formal language">formal language</a> is <b>recursive</b> if there exists a Turing machine that <a href="Decider_(Turing_machine)" title="Decider (Turing machine)">decides</a> the formal language.<sup id="cite_ref-FOOTNOTESipser2012_1-0" class="reference"><a href="#cite_note-FOOTNOTESipser2012-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, such always-halting Turing machines are called <a href="Total_Turing_machine" class="mw-redirect" title="Total Turing machine">total Turing machines</a> or <b>algorithms</b>.<sup id="cite_ref-FOOTNOTESipser1997_2-0" class="reference"><a href="#cite_note-FOOTNOTESipser1997-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>The concept of <b>decidability</b> may be extended to other <a href="Models_of_computation" class="mw-redirect" title="Models of computation">models of computation</a>. For example, one may speak of languages decidable on a <a href="Non-deterministic_Turing_machine" class="mw-redirect" title="Non-deterministic Turing machine">non-deterministic Turing machine</a>. Therefore, whenever an ambiguity is possible, the synonym used for "recursive language" is <b>Turing-decidable language</b>, rather than simply <i>decidable</i>.

</p><p>The class of all recursive languages is often called <b><a href="R_(complexity)" title="R (complexity)">R</a></b>, although this name is also used for the class <a href="RP_(complexity)" title="RP (complexity)">RP</a>.

</p><p>This type of language was not defined in the <a href="Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a>.<sup id="cite_ref-FOOTNOTEChomsky1959_3-0" class="reference"><a href="#cite_note-FOOTNOTEChomsky1959-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> All recursive languages are also <a href="Recursively_enumerable_language" title="Recursively enumerable language">recursively enumerable</a>. All <a href="Regular_language" title="Regular language">regular</a>, <a href="Context-free_language" title="Context-free language">context-free</a> and <a href="Context-sensitive_language" title="Context-sensitive language">context-sensitive</a> languages are recursive.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

<p>There are two equivalent major definitions for the concept of a recursive language:

</p>

<ol><li>A recursive language is a <a href="Recursive_set" class="mw-redirect" title="Recursive set">recursive</a> subset of the set of all possible finite-length <a href="Formal_language" title="Formal language">words</a> over an <a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">alphabet</a>.</li>

<li>A recursive language is a <a href="Formal_language" title="Formal language">formal language</a> for which there exists a <a href="Turing_machine" title="Turing machine">Turing machine</a> that <a href="Decider_(Turing_machine)" title="Decider (Turing machine)">decides</a> it.</li></ol>

<p>On the other hand, we can show that a <a href="Decision_problem" title="Decision problem">decision problem</a> is decidable by exhibiting a Turing machine running an <a href="Algorithm" title="Algorithm">algorithm</a> that terminates on all inputs. An <a href="Undecidable_problem" title="Undecidable problem">undecidable problem</a> is a problem that is not decidable.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set <i>L={abc, aabbcc, aaabbbccc, ...}</i>;

more formally, the set

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}}</annotation>

</semantics>

</math></span><img src="./1cfce8a81b9436ef00e1c936618b6b9ea9f4f365.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.786ex; height:2.843ex;" alt="{\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}}" loading="lazy"></span></dd></dl>

<p>is context-sensitive and therefore recursive.

</p><p>Examples of decidable languages that are not context-sensitive are more difficult to describe. For one such example, some familiarity with <a href="Mathematical_logic" title="Mathematical logic">mathematical logic</a> is required: <a href="Presburger_arithmetic" title="Presburger arithmetic">Presburger arithmetic</a> is the first-order theory of the natural numbers with addition (but without multiplication). While the set of <a href="First-order_logic#Formulas" title="First-order logic">well-formed formulas</a> in Presburger arithmetic is context-free, every deterministic Turing machine accepting the set of true statements in Presburger arithmetic has a worst-case runtime of at least <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2^{pn}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2^{pn}}}</annotation>

</semantics>

</math></span><img src="./ba54fdec95fae2f8b8ac4d0bd6900ba469b904b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.853ex; height:2.676ex;" alt="{\displaystyle 2^{2^{pn}}}" loading="lazy"></span>, for some constant <i>p</i>>0.<sup id="cite_ref-FOOTNOTEFischerRabin1974_4-0" class="reference"><a href="#cite_note-FOOTNOTEFischerRabin1974-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Here, <i>n</i> denotes the length of the given formula. Since every context-sensitive language can be accepted by a <a href="Linear_bounded_automaton" title="Linear bounded automaton">linear bounded automaton</a>, and such an automaton can be simulated by a deterministic Turing machine with worst-case running time at most <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n}}</annotation>

</semantics>

</math></span><img src="./31246d3db82f98a975bd9d9a5ea525679f89ff6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.298ex; height:2.676ex;" alt="{\displaystyle q^{n}}" loading="lazy"></span> for some constant <i>q</i>,<sup id="cite_ref-FOOTNOTEBook1974_5-0" class="reference"><a href="#cite_note-FOOTNOTEBook1974-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> the set of valid formulas in Presburger arithmetic is not context-sensitive. On a positive side, it is known that there is a deterministic Turing machine running in time at most triply exponential in <i>n</i> that decides the set of true formulas in Presburger arithmetic.<sup id="cite_ref-FOOTNOTEOppen1978_6-0" class="reference"><a href="#cite_note-FOOTNOTEOppen1978-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Thus, this is an example of a language that is decidable but not context-sensitive.

</p>

<div class="mw-heading mw-heading2"><h2 id="Closure_properties">Closure properties</h2></div>

<p>Recursive languages are <a href="Closure_(mathematics)" title="Closure (mathematics)">closed</a> under the following operations. That is, if <i>L</i> and <i>P</i> are two recursive languages, then the following languages are recursive as well:

</p>

<ul><li>The <a href="Kleene_star" title="Kleene star">Kleene star</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L^{*}}</annotation>

</semantics>

</math></span><img src="./d9a3547ba2f3cc5cb4463473815f227092b4766a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.637ex; height:2.343ex;" alt="{\displaystyle L^{*}}" loading="lazy"></span></li>

<li>The image φ(L) under an <a href="Homomorphism#Formal_language_theory" title="Homomorphism">e-free homomorphism</a> φ</li>

<li>The concatenation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\circ P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\circ P}</annotation>

</semantics>

</math></span><img src="./eae46ff0ba4ad8c9e2b9cfab9f0b08ce37bd1581.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.523ex; height:2.176ex;" alt="{\displaystyle L\circ P}" loading="lazy"></span></li>

<li>The union <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\cup P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\cup P}</annotation>

</semantics>

</math></span><img src="./09e9fef5be936343caeb70e10b5e9448b12705a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.911ex; height:2.176ex;" alt="{\displaystyle L\cup P}" loading="lazy"></span></li>

<li>The intersection <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\cap P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\cap P}</annotation>

</semantics>

</math></span><img src="./7ddfcbe07573129fe82433653ce72e025487c14f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.911ex; height:2.176ex;" alt="{\displaystyle L\cap P}" loading="lazy"></span></li>

<li>The complement of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span></li>

<li>The set difference <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L-P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L-P}</annotation>

</semantics>

</math></span><img src="./7307b31a7222c63769f36164b281b1654f485aae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.169ex; height:2.343ex;" alt="{\displaystyle L-P}" loading="lazy"></span></li></ul>

<p>The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

</p>

<ul><li><a href="Recursively_enumerable_language" title="Recursively enumerable language">Recursively enumerable language</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-FOOTNOTESipser2012-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTESipser2012_1-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFSipser2012">Sipser (2012)</a>.</span>

</li>

<li id="cite_note-FOOTNOTESipser1997-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTESipser1997_2-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFSipser1997">Sipser (1997)</a>.</span>

</li>

<li id="cite_note-FOOTNOTEChomsky1959-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEChomsky1959_3-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFChomsky1959">Chomsky (1959)</a>.</span>

</li>

<li id="cite_note-FOOTNOTEFischerRabin1974-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEFischerRabin1974_4-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFFischerRabin1974">Fischer & Rabin (1974)</a>.</span>

</li>

</li>

<li id="cite_note-FOOTNOTEOppen1978-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEOppen1978_6-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFOppen1978">Oppen (1978)</a>.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBook1974" class="citation journal cs1"><a href="Ronald_V._Book" title="Ronald V. Book">Book, Ronald V.</a> (1974). "Comparing complexity classes". <i><a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>. <b>9</b>: <span class="nowrap">213–</span>229. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2874%2980008-5">10.1016/S0022-0000(74)80008-5</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0366099">0366099</a>.</cite></li>

<li><cite id="CITEREFChomsky1959" class="citation journal cs1">Chomsky, Noam (1959). "On certain formal properties of grammars". <i>Information and Control</i>. <b>2</b> (2): <span class="nowrap">137–</span>167. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0019-9958%2859%2990362-6">10.1016/S0019-9958(59)90362-6</a>.</cite></li>

<li><cite id="CITEREFFischerRabin1974" class="citation journal cs1"><a href="Michael_J._Fischer" title="Michael J. Fischer">Fischer, Michael J.</a>; <a href="Michael_O._Rabin" title="Michael O. Rabin">Rabin, Michael O.</a> (1974). <a rel="nofollow" class="external text" href="http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps">"Super-Exponential Complexity of Presburger Arithmetic"</a>. <i>Proceedings of the SIAM-AMS Symposium in Applied Mathematics</i>. <b>7</b>: <span class="nowrap">27–</span>41.</cite></li>

<li><cite id="CITEREFOppen1978" class="citation journal cs1">Oppen, Derek C. (1978). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2878%2990021-1">"A 2<sup>2<sup>2<sup><i>pn</i></sup></sup></sup> Upper Bound on the Complexity of Presburger Arithmetic"</a>. <i>J. Comput. Syst. Sci</i>. <b>16</b> (3): <span class="nowrap">323–</span>332. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2878%2990021-1">10.1016/0022-0000(78)90021-1</a></span>.</cite></li>

<li><cite id="CITEREFSipser1997" class="citation book cs1"><a href="Michael_Sipser" title="Michael Sipser">Sipser, Michael</a> (1997). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/151">"Decidability"</a></span>. <i>Introduction to the Theory of Computation</i>. PWS Publishing. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoth00sips/page/151">151–170</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-534-94728-6</bdi>.</cite></li>

<li><cite id="CITEREFSipser2012" class="citation book cs1"><a href="Michael_Sipser" title="Michael Sipser">Sipser, Michael</a> (2012). "The Church-Turing Thesis". <i>Introduction to the Theory of Computation</i>. Cengage Learning. p. 170. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-133-18779-0</bdi>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Automata_theory:_formal_languages_and_formal_grammars385" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Automata_theory:_formal_languages_and_formal_grammars385" style="font-size:114%;margin:0 4em"><a href="Automata_theory" title="Automata theory">Automata theory</a>: <a href="Formal_language" title="Formal language">formal languages</a> and <a href="Formal_grammar" title="Formal grammar">formal grammars</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd plainlist" style="width:100%;padding:0;background:transparent;color:inherit;"><div style="padding:0px"><table class="navbox-columns-table" style="border-spacing: 0px; text-align:left;width:100%;"><tbody><tr><td class="navbox-abovebelow" style="font-weight:bold;"><a href="Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="Formal_grammar" title="Formal grammar">Grammars</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="Formal_language" title="Formal language">Languages</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="Abstract_machine" title="Abstract machine">Abstract machines</a></td></tr><tr style="vertical-align:top"><td class="navbox-list" style="padding:0px;text-align: center;width:10em;"><div>

</div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div>

<ul><li><a href="Unrestricted_grammar" title="Unrestricted grammar">Unrestricted</a></li>

<li>(no common name)</li>

<li><a href="Context-sensitive_grammar" title="Context-sensitive grammar">Context-sensitive</a></li>

<li><span style="white-space:nowrap;">Positive <a href="Range_concatenation_grammars" class="mw-redirect" title="Range concatenation grammars">range concatenation</a></span></li>

<li><a href="Indexed_grammar" title="Indexed grammar">Indexed</a></li>

<li><a href="Linear_context-free_rewriting_system" class="mw-redirect" title="Linear context-free rewriting system">Linear context-free rewriting systems</a></li>

<li><a href="Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li>

<li><a href="Context-free_grammar" title="Context-free grammar">Context-free</a></li>

<li><a href="Deterministic_context-free_grammar" title="Deterministic context-free grammar">Deterministic context-free</a></li>

<li><a href="Nested_word" title="Nested word">Visibly pushdown</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular</a></li>

<li><a href="Non-recursive_grammar" class="mw-redirect" title="Non-recursive grammar">Non-recursive</a></li></ul>

</div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div>

<ul><li><a href="Recursively_enumerable_language" title="Recursively enumerable language">Recursively enumerable</a></li>

<li><a href="Context-sensitive_language" title="Context-sensitive language">Context-sensitive</a></li>

<li><span style="white-space:nowrap;">Positive <a href="Range_concatenation_language" class="mw-redirect" title="Range concatenation language">range concatenation</a><sup>*</sup></span></li>

<li><a href="Indexed_language" title="Indexed language">Indexed</a><sup>*</sup></li>

<li><a href="Linear_context-free_rewriting_language" class="mw-redirect" title="Linear context-free rewriting language">Linear context-free rewriting language</a></li>

<li><a href="Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li>

<li><a href="Context-free_language" title="Context-free language">Context-free</a></li>

<li><a href="Deterministic_context-free_language" title="Deterministic context-free language">Deterministic context-free</a></li>

<li><a href="Nested_word" title="Nested word">Visibly pushdown</a></li>

<li><a href="Regular_language" title="Regular language">Regular</a></li>

<li><a href="Finite_language" class="mw-redirect" title="Finite language">Finite</a></li></ul>

</div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div>

<ul><li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Decider_(Turing_machine)" title="Decider (Turing machine)">Decider</a></li>

<li><a href="Linear_bounded_automaton" title="Linear bounded automaton">Linear-bounded</a></li>

<li><a href="PTIME" class="mw-redirect" title="PTIME">PTIME</a> Turing Machine</li>

<li><a href="Nested_stack_automaton" title="Nested stack automaton">Nested stack</a></li>

<li><a href="Thread_automaton" title="Thread automaton">Thread automaton</a></li>

<li>restricted <a href="Tree_stack_automaton" title="Tree stack automaton">Tree stack automaton</a></li>

<li><a href="Embedded_pushdown_automaton" title="Embedded pushdown automaton">Embedded pushdown</a></li>

<li><a href="Pushdown_automaton" title="Pushdown automaton">Nondeterministic pushdown</a></li>

<li><a href="Deterministic_pushdown_automaton" title="Deterministic pushdown automaton">Deterministic pushdown</a></li>

<li><a href="Nested_word" title="Nested word">Visibly pushdown</a></li>

<li><a href="Finite-state_machine" title="Finite-state machine">Finite</a></li>

<li><a href="Aperiodic_finite_state_automaton" class="mw-redirect" title="Aperiodic finite state automaton">Counter-free (with aperiodic finite monoid)</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Acyclic finite</a></li></ul>

</div></td></tr></tbody></table></div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><span style="white-space:nowrap;">Each category of languages, except those marked by a <sup>*</sup>, is a <a href="Proper_subset" class="mw-redirect" title="Proper subset">proper subset</a> of the category directly above it.</span> <span style="white-space:nowrap;">Any language in each category is generated by a grammar and by an automaton in the category in the same line.</span></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-14" href="https://en.wikipedia.org/wiki/?title=Recursive_language&oldid=1300431324">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>